#include "graph.h"
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "util/mt.h"

// static void connect_segment (Graph* graph, int index, Cbuf* paths);

void graph_init (Graph* graph, int n_segments)
{
	assert(graph != NULL);
	assert(n_segments >= 2); // need at least spawn + goal

	graph->n_segments = n_segments;
	graph->segment = malloc (graph->n_segments * sizeof (Segment));
	graph->path = trimatrix_alloc (n_segments);
}

void graph_cleanup (Graph* graph)
{
	assert(graph != NULL);
	
	free (graph->segment);
	trimatrix_free (graph->path);
	memset (graph, 0, sizeof(Graph));
}

// Future directions for balancing:
// Make the generator more intelligent wrt paths.
// There must not be one path with only treasure
// and another with only monsters.
void graph_generate (Graph* graph, int n_players, unsigned int seed)
{
	assert(graph != NULL);
	assert(n_players > 0);

	mt_seed (seed);

	graph->segment[0].type = ST_SPAWN;
	graph->segment[0].intensity = n_players;
	graph->segment[graph->n_segments-1].type = ST_GOAL;
	graph->segment[graph->n_segments-1].intensity = n_players;

	// segment content
	for (int i = 1; i < graph->n_segments-1; i++) {
		graph->segment[i].type = mt_rand () % 9 + 2;
		graph->segment[i].intensity = i * 10 / graph->n_segments + mt_rand() % 5;
	}

	// connections
	for (int i = 0; i < graph->n_segments-1; ++i) {
		int j = i + 1;
		for (int k = 0; k < n_players; k++) {
			j += mt_rand() % 3;
			if (j >= graph->n_segments)	{
				j = graph->n_segments-1;
			}
			trimatrix_set (graph->path, i, j, 1);
		}
	}	

	// Old graph_generate: Does not use trimatrix, but paths, entrances and branches for
	// the segments.
	/*
	int min_paths = MAX(n_players*2,MAX_ROOTS);
	int max_paths = MAX(n_players*6,min_paths*2);
	
	int n_challenges = graph->n_segments;
	Segment* challenge = malloc (n_challenges * sizeof (Segment));
	
	Cbuf paths;
	cbuf_init (&paths, sizeof(Segment*), MAX(max_paths*2,MAX_BRANCHES*2));
	
	// The current generator implementation: Generates spawns for all
	// the players, then generates a lot of segments at random, then
	// attempts to connect them together using corridors to stay within
	// a min/max range of open paths.
	mt_seed(seed);
	
	for (int i = 0; i < n_players; i++)
	{
		segment_generate (&graph->segment[i], ST_SPAWN, 0);
		graph->segment[i].n_branches = 0; // handled manually later
	}
	
	for (int i = 0; i < n_challenges; i++)
	{
		int intensity = 5;
		SegmentTypeId type = (mt_rand() % 4) + ST_MONSTERS;
		segment_generate (&challenge[i], type, intensity);
	}
	
	// initial paths
	for (int i = 0; i < min_paths; i++) {
		Segment* start_path = &graph->segment[i%n_players];
		cbuf_push(&paths, &start_path);
	}
	
	int s = n_players; // insert index
	
	for (int i = 0; i < n_challenges; i++) {		
		graph->segment[s] = challenge[i];
		connect_segment (graph, s++, &paths);
		
		while (paths.count < min_paths) {
			int n_roots = SEGTYPE[ST_CORRIDOR].min_roots;
			int n_branches = MIN(min_paths-paths.count+n_roots,SEGTYPE[ST_CORRIDOR].max_branches);
			segment_make_support_corridor (&graph->segment[s], n_roots, n_branches);
			connect_segment (graph, s++, &paths);
		}
		while (paths.count > max_paths) {
			int n_branches = SEGTYPE[ST_CORRIDOR].min_branches;
			int n_roots = MIN(paths.count-max_paths+n_branches,SEGTYPE[ST_CORRIDOR].max_roots);
			segment_make_support_corridor (&graph->segment[s], n_roots, n_branches);
			connect_segment (graph, s++, &paths);
		}
	}
	
	// Finish with a single exit
	while (paths.count > SEGTYPE[ST_GOAL].max_roots) {
		int n_roots = MIN(paths.count,SEGTYPE[ST_CORRIDOR].max_roots);
		segment_make_support_corridor (&graph->segment[s], n_roots, 1);
		connect_segment (graph, s++, &paths);
	}
	
	segment_make_goal (&graph->segment[s], paths.count);
	connect_segment (graph, s++, &paths);
	graph->n_segments = s;
	
	cbuf_cleanup (&paths);
	
	assert(graph->n_segments < graph->segments_size);
	assert(paths.count == 0);
	*/
}

/*
// Takes some paths from loose_path, sticks them into the segment, 
// and returns the segment exit paths to the loose_path array.
static void connect_segment (Graph* graph, int index, Cbuf* paths)
{
	Segment* s = &graph->segment[index];
	
	assert (s->n_roots <= paths->count);
	
	for (int i = 0; i < s->n_roots; i++) {
		Segment* p = *CBUF_POP(paths,Segment*);
		s->root[i] = p;
		p->branch[p->n_branches++] = s;
	}
	
	for (int i = 0; i < s->n_branches; i++) {
		assert(!cbuf_full(paths));
		cbuf_push (paths, &s);
	}
	
	s->n_branches = 0; // Will be counted up again when paths are picked up
}

int graph_count_rooms (Graph* graph)
{
	int n_rooms = 0;
	
	for (int i = 0; i < graph->n_segments; i++)
	{
		n_rooms += graph->segment[i].type->max_rooms;
	}
	
	return n_rooms;
}
*/

#ifdef TEST_GRAPH
#include <stdio.h>

static void print_segment (Graph* graph, Segment* s)
{
	printf ("%zd:%s ", s - graph->segment, s->type->name);
}

static void print_graph (Graph* graph)
{
	for (int i = 0; i < graph->n_segments; i++)
	{
		Segment* s = &graph->segment[i];
		for (int j = 0; j < s->n_roots; j++)
		{
			print_segment (graph, s->root[j]);
		}
		printf ("-> * ");
		print_segment (graph, s);
		printf ("* -> ");
		for (int j = 0; j < s->n_branches; j++)
		{
			print_segment (graph, s->branch[j]);
		}
		printf ("\n");
	}
}

int main ()
{
	int players = 2;
	int extent = 20;
	unsigned int seed = 4711;
	
	Graph graph;
	graph_init (&graph, players, extent);
	printf ("Graph has %d segments, space for %d\n", graph.n_segments, graph.segments_size);
	
	graph_generate (&graph, players, seed);
	print_graph (&graph);
	
	graph_cleanup (&graph);
	return 0;
}
#endif

